package com.wm.algorithm.array;

/**
 * @ClassName: BaseArray
 * @Description: 基础数组
 * @Author: wm
 * @Date: 2024/1/2 10:24
 */
public class BaseArray {
    public static void main(String[] args) {
        int[] arr = new int[]{28, 8, 10, 23, 21, 19, 9};
        //从小到大排序
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 堆排序
     * 思路：首先进行数组建堆；交换根节点和尾部元素，然后重新建堆；
     * 重复上述过程，直到根节点和尾部元素交换完毕
     */
    public static void heapSort(int[] nums) {
        // 获取数组长度
        int length = nums.length;
        // 数组索引为i的元素的父节点的下标索引为：i-1/2
        // 因为下标从0开始，最后一个子节点（length-1）减去1再除以2得到父节点(length-1-1)/2=length/2-1
        // 从最后一个节点开始遍历直到根节点（父节点会和子节点进行比较）
        for (int i = length / 2 - 1; i >= 0; i--) {
            // 把数组转化为堆，又称为建堆
            buildHeap(nums, i, length);
        }

        // 因为之前建堆了，这意味着根结点就是我们需要的值
        for (int i = length - 1; i >= 0; i--) {
            // 将当前根节点和未排序的最大子节点进行交换
            swap(nums, 0, i);
            // 剩下的元素继续建堆，要理解i--，刚刚交换的根节点的值就是已经排序的不会参与遍历了
            buildHeap(nums, 0, i);
        }
    }

    private static void buildHeap(int[] nums, int i, int length) {
        // 大顶堆的节点调整
        while (true) {
            // 定义最大节点的位置
            int maxPos = i;
            // 排查在未排序的列表中，当前节点的值是不是小于他的左子节点（2*i+1）
            if (i * 2 + 1 < length && nums[i] < nums[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            // 检查在未排序列表中，同时当前的最大节点和i节点的右子节点（2i+2）也比较，找出最大值的节点
            // 也就是找出父节点，左节点，右节点三者中的最大节点值
            if (i * 2 + 2 < length && nums[maxPos] < nums[i * 2 + 2]) {
                maxPos = i * 2 + 2;
            }
            // maxPos没变说明已经找不到比当前节点大的了
            if (maxPos == i) {
                break;
            }
            // 交换两个节点（当前节点和最大值的节点进行交换）
            // 这里就是父节点和子节点中那个较大的节点进行交换
            swap(nums, i, maxPos);
            // 继续往下处理这个过程也就是继续处理最大节点，看它是否满足大根堆的条件（比它的子节点都大）
            i = maxPos;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static int parent(int i) {
        return (i - 1) / 2;
    }

    private int left(int i) {
        return i * 2 + 1;
    }

    private int right(int i) {
        return i * 2 + 2;
    }

    /**
     * 选择排序
     * 思路：从序列中找出最大的那个元素，然后和最末尾的元素交换位置。执行完一轮后，最末尾的那个元素就是最大的元素。
     *
     * @param nums
     */
    // O(n^2)/O(1)
    public static void selectSort(int[] nums) {
        for (int end = nums.length - 1; end > 0; end--) {
            int max = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (nums[begin] > nums[max]) {
                    max = begin;
                }
            }
            int temp = nums[end];
            nums[end] = nums[max];
            nums[max] = temp;
        }
    }

    /**
     * 冒泡排序
     * 思路：加入优化的解法，相邻元素比较大小，前者比后者大就交换位置，执行完一轮末端就是最大的元素，
     * 记录排好序的位置，每次更新
     *
     * @param nums
     */
    // O(n^2)/O(1)
    public static void bubbleSort(int[] nums) {
        for (int end = nums.length - 1; end > 0; end--) {
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                if (nums[begin - 1] > nums[begin]) {
                    int temp = nums[begin - 1];
                    nums[begin - 1] = nums[begin];
                    nums[begin] = temp;
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }
}
